<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html><head><title>Programming in Lua : 11.3</title>
<link rel="stylesheet" type="text/css" href="pil.css">
</head>
<body>
<p class="warning">
<A HREF="contents.html"><IMG TITLE="Programming in Lua (first edition)" SRC="capa.jpg" ALT="" ALIGN="left"></A>This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.<BR>The third edition targets Lua 5.2 and is available at <A HREF="http://www.amazon.com/exec/obidos/ASIN/859037985X/theprogrammil3-20">Amazon</A> and other bookstores.<BR>By buying the book, you also help to <A HREF="../donations.html">support the Lua project</A>.
</p>
<table width="100%" class="nav">
<tr>
<td width="10%" align="left"><a href="11.2.html"><img border="0" src="left.png" alt="Previous"></a></td>
<td width="80%" align="center"><a href="contents.html"><font face="Helvetica,Arial,sanserif">
<font color="gray">Programming in </font><font color="blue"> Lua</font>
</font></a></td>
<td width="10%" align="right"><a href="11.4.html"><img border="0" src="right.png" alt="Next"></a></td>
</tr>
<tr>
<td width="10%" align="left"></td>
<td width="80%" align="center"><a href="contents.html#P2">Part II. Tables and Objects</a>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<a href="contents.html#11">Chapter 11. Data Structures</a></td>
<td width="10%" align="right"></td></tr>
</table>
<hr/>
<p><h2>11.3 &ndash; Linked Lists</h2>

<p>Because tables are dynamic entities,
it is easy to implement linked lists in Lua.
Each node is represented by a table
and links are simply table fields that contain references
to other tables.
For instance,
to implement a basic list,
where each node has two fields, <code>next</code> and <code>value</code>,
we need a variable to be the list root:
<pre>
    list = nil
</pre>
To insert an element at the beginning of the list,
with a value <code>v</code>, we do
<pre>
    list = {next = list, value = v}
</pre>
To traverse the list, we write:
<pre>
    local l = list
    while l do
      print(l.value)
      l = l.next
    end
</pre>

<p>Other kinds of lists,
such as double-linked lists or circular lists,
are also implemented easily.
However, you seldom need those structures in Lua,
because usually there is a simpler way to represent your data
without using lists.
For instance,
we can represent a stack with an (unbounded) array,
with a field <code>n</code> pointing to the top.

<hr/>
<table width="100%" class="nav">
<tr valign="top">
<td width="90%" align="left">
<small>
  Copyright &copy; 2003&ndash;2004 Roberto Ierusalimschy.  All rights reserved.
</small>
</td>
<td width="10%" align="right"><a href="11.4.html"><img border="0" src="right.png" alt="Next"></a></td>
</tr>
</table>


</body></html>

